#include <omp.h>
#include <stdio.h>

#define MAX_NUM_OF_CHILDREN     4
#define NUM_OF_CHILDPOINTS      2
#define MAX_NUM_OF_PROCESS      32
#define TRUE                    1
#define FALSE                   0

static int num_of_process = 4;

struct OMPNode {
    int parentsense;
    int *parentpointer;
    int *childpointers[NUM_OF_CHILDPOINTS];
    int havechild[MAX_NUM_OF_CHILDREN];
    int childnotready[MAX_NUM_OF_CHILDREN];
};
static struct OMPNode nodes[MAX_NUM_OF_PROCESS];
static int dummy;
static int ompsense = TRUE;
#pragma omp threadprivate(ompsense)

void init_tree_barrier_omp(int nump)
{
    int i, j;
    dummy = FALSE;
    num_of_process = nump;
    
    if (num_of_process > MAX_NUM_OF_PROCESS) 
        num_of_process = MAX_NUM_OF_PROCESS;

    for (i=0; i<num_of_process; ++i) {
        for (j=0; j<MAX_NUM_OF_CHILDREN; ++j) {
            if ((i*4)+j+1 < num_of_process) 
                nodes[i].havechild[j] = TRUE;
            else 
                nodes[i].havechild[j] = FALSE;
            nodes[i].childnotready[j] = nodes[i].havechild[j];
        }
        
        nodes[i].parentpointer = (i == 0) ? &dummy : 
            &nodes[(i-1)/4].childnotready[(i-1)%4];
        
        nodes[i].childpointers[0] = (2*i+1>=num_of_process) ? &dummy :
            &nodes[i*2+1].parentsense;
        nodes[i].childpointers[1] = (2*i+2>=num_of_process) ? &dummy :
            &nodes[i*2+2].parentsense;
        
        nodes[i].parentsense = FALSE;
    }
}

void waiting_for_children(int *p, int vpid)
{
    int i;
    do {
        for (i=0; i<MAX_NUM_OF_CHILDREN; ++i)
            if (*(p + i)) break;
    } while (i < MAX_NUM_OF_CHILDREN);
}

void reset_childnotready(int *p, int vpid)
{
    int i;
    for (i=0; i<MAX_NUM_OF_CHILDREN; ++i) {
        *(p + i) = nodes[vpid].havechild[i];
    }
}

void waiting_for_parentsense(int *p, int vpid)
{
    if (vpid != 0) while (*p != ompsense);
}

void tree_barrier_omp()
{
    int i;
    int vpid = omp_get_thread_num();
    int *p = &nodes[vpid].childnotready[0];
    // repeat until childnotready = {false, false, false, false}
    waiting_for_children(p, vpid);
    /*
    p = &nodes[vpid].childnotready[0];
    do {
        for (i=0; i<MAX_NUM_OF_CHILDREN; ++i)
            if (*(p + i)) break;
    } while (i < MAX_NUM_OF_CHILDREN);
    */

    // childnotready := havechild
    reset_childnotready(p, vpid);
    /*for (i=0; i<MAX_NUM_OF_CHILDREN; ++i) {
        *(p + i) = nodes[vpid].havechild[i];
    }
    */

    // parentpointer^ := false
    //atomic_decrease(nodes[vpid].parentpointer);
    p = nodes[vpid].parentpointer;
    --*p;

    // if vpid != 0
    //    repeat until parentsense = sense
    p = &nodes[vpid].parentsense;
    waiting_for_parentsense(p, vpid);
    //if (vpid != 0) while (*p != ompsense);
}

void release_barrier_omp()
{
    int vpid = omp_get_thread_num();

    // childpointers[0]^ := sense
    // childpionters[1]^ := sense
    int *p1 = nodes[vpid].childpointers[0];
    int *p2 = nodes[vpid].childpointers[1];
    if (ompsense) {
        //atomic_increase(nodes[vpid].childpointers[0]);
        //atomic_increase(nodes[vpid].childpointers[1]);
        ++*p1;
        ++*p2;
    }
    else {
        //atomic_decrease(nodes[vpid].childpointers[0]);
        //atomic_decrease(nodes[vpid].childpointers[1]);
        --*p1;
        --*p2;
    }

    // sense := not sense
    ompsense = 1 - ompsense;
}

void omp_tree_barrier()
{
    tree_barrier_omp();
    release_barrier_omp();
}
